package com.cty._05_Ability._53_01_NumberOfK;

/**
 * @Auther: cty
 * @Date: 2020/7/21 15:48
 * @Description: 面试题53（一）：数字在排序数组中出现的次数
 * 题目：统计一个数字在排序数组中出现的次数。例如输入排序数组{1, 2, 3, 3,
 * 3, 3, 4, 5}和数字3，由于3在这个数组中出现了4次，因此输出4。
 * @version: 1.0
 */
public class NumberOfK {

    /**
     * 二分法实现
     * 时间复杂度  O(logN)
     * @param sortedArray
     * @param k
     * @return
     */
    public static int numberOfK(int[] sortedArray, int k){
        if(sortedArray==null || sortedArray.length==0)
            return 0;

        int firstKIndex = getFirstKIndex(sortedArray, k);
        int lastKIndex = getLastKIndex(sortedArray, k);

        if(firstKIndex==-1 || lastKIndex==-1)
            return 0;
        return lastKIndex - firstKIndex + 1;
    }  // end numberOfK()

    private static int getFirstKIndex(int[] sortedArray, int k){
        int lowerBound = 0;
        int upperBound = sortedArray.length - 1;
        while(true){
            if(lowerBound > upperBound)
                return -1;

            int medianIndex = lowerBound + ((upperBound-lowerBound)>>1);
            if(sortedArray[medianIndex] == k){
                if(medianIndex==0 || (medianIndex>0 && sortedArray[medianIndex-1]!=k))
                    return medianIndex;
                else
                    upperBound = medianIndex - 1;
            }else if(sortedArray[medianIndex] > k)
                upperBound = medianIndex - 1;
            else
                lowerBound = medianIndex + 1;
        }  // end while

    }  // end getFirstKIndex()

    private static int getLastKIndex(int[] sortedArray, int k){
        int lowerBound = 0;
        int upperBound = sortedArray.length - 1;

        while(true){
            if(lowerBound > upperBound)
                return -1;

            int medianIndex = lowerBound + ((upperBound-lowerBound)>>1);
            if(sortedArray[medianIndex] == k){
                if(medianIndex==sortedArray.length-1 || (medianIndex<sortedArray.length-1 && sortedArray[medianIndex+1]!=k))
                    return medianIndex;
                else
                    lowerBound = medianIndex + 1;
            }else if(sortedArray[medianIndex] < k)
                lowerBound = medianIndex + 1;
            else
                upperBound = medianIndex - 1;
        }  // end while
    }  // end getLastKIndex()

}  // end class
